package algocasts;

public class P139_LowestCommonAncestorOfABinarySearchTree {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    // Time: O(h)  Space: O(h)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }

    // Time: O(h)  Space: O(1)
    public TreeNode lowestCommonAncestor_Iterative(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val)
                root = root.left;
            else if (p.val > root.val && q.val > root.val)
                root = root.right;
            else return root;
        }
        return null;
    }

}
